#pragma once
#include <iostream>
#include <vector>
using namespace std;

enum State
{
	EMPTY,
	EXIST,
	DELETE
};

template<class K, class V>
struct HashData
{
	pair<K, V> _kv;
	State _state = EMPTY;
};

template<class K, class V>
class HashTable
{
public:
	HashData<K, V>* Find(const K& key)
	{
		if (_table.size() == 0)
		{
			return nullptr;
		}

		size_t start = key % _table.size();
		size_t index = start;
		size_t i = 1;
		while (_table[index]._state != EMPTY)
		{
			if (_table[index]._state == EXIST && _table[index]._kv.first == key)
				return	&_table[index];

			index = start + i;
			index %= _table.size();
			i++;
		}

		return nullptr;
	}

	bool Insert(const pair<K, V>& kv)
	{
		HashData<K, V>* ret = Find(kv.first);
		if (ret)
			return false;

		if (_table.size() == 0)
		{
			_table.resize(10);
		}
		else if ((double)_n / (double)_table.size() > 0.7)
		{
			HashTable<K, V> newHT;
			newHT._table.resize(2 * _table.size());
			for (auto& e : _table)
			{
				if (e._state == EXIST)
				{
					newHT.Insert(e._kv);
				}
			}

			_table.swap(newHT._table);
		}

		size_t start = kv.first % _table.size();
		size_t index = start;
		size_t i = 1;
		size_t base = index;
		while (_table[index]._state == EXIST)
		{
			index = start + i;
			index %= _table.size();
			i++;
		}	 
		_table[index]._kv = kv;
		_table[index]._state = EXIST;

		_n++;
		return true;
	}
	
	bool Erase(const K& key)
	{
		HashData<K, V>* ret = Find(key);
		if (ret)
		{
			ret->_state = DELETE;
			_n--;
			return true;
		}
		return false;
	}
	
private:
	vector<HashData<K, V>> _table;
	size_t _n = 0;
};